package com.julius.design.suanfa.linked;

/**
 * @author julius
 * @date 2021-11-02 上午 10:40
 * <p>
 *      合并有序链表
 *      输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 *
 *      https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
 * </p>
 */
public class MergeSortList {


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        //临界条件
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        //合并，这里l1 和 l2 都不是null

        ListNode c1 = l1;

        ListNode c2 = l2;

        ListNode p1,p2;

        //伪头结点，避免多次判断
        ListNode ans = new ListNode(0);

        ListNode ansc = ans;

        /**
         * 优化性能的地方在于哪里？
         *      增加伪头节点减少逻辑判断
         */
        //遍历链表
        while(c1 != null && c2 != null){
            if(c1.val <= c2.val){
                p1 = c1;
                c1 = c1.next;
                p1.next = null;
                ansc.next = p1;
                ansc = ansc.next;
            }else{
                p2 = c2;
                c2 = c2.next;
                p2.next = null;
                ansc.next = p2;
                ansc = ansc.next;
            }
        }
        if(c1 == null){
            ansc.next = c2;
        }

        if(c2 == null){
            ansc.next = c1;
        }
        return ans.next;

    }

    /**
     * Definition for singly-linked list.
     *
     */
    public class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
    }
}
